package MyGraph;

import Queue.LinkQueue;

public class BFS {
    // 图的广度优先算法遍历操作

    // 标识数组
    int[] visited;
    public void BFSTraverse(IGraph g)throws Exception{
        // 建立顶点访问标识数组
        visited = new int[g.getVNum()];

        // 以每一个顶点开始遍历
        for(int i=0; i<g.getVNum(); i++){
            if(visited[i]==0) {
                BFS(g, i);
            }
        }
    }

    public void BFS(IGraph g, int i)throws Exception{
        // 标记该顶点已经被访问过了
        visited[i] = 1;
        // 输出顶点的信息数据
        System.out.println(g.getVex(i).toString()+" ");
        // 建立辅助队列
        LinkQueue q = new LinkQueue();
        // 将该顶点入队列
        q.offer(i);
        // 如果队列没有为空 就出队列
        while(!q.isEmpty()){
            int u = (int) q.poll();
            // firstAdj(u) 如果没有匹配到邻顶点就会返回 -1
            // nextAdj 由于for循环体这个方法 所以会把该层级循环输出
            for(int v=g.firstAdj(u); v>=0; v=g.nextAdj(u, v)){
               if(visited[v]==0){
                   System.out.println(g.getVex(v).toString()+" ");
                   visited[v] = 1;
                   q.offer(v);
               }
            }
        }

    }


}
